package leetcode.leetcode_hot100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 岛屿数量
 */
public class T0200 {
    class Solution {
        int m,n;
        public int numIslands(char[][] grid) {
            m=grid.length;
            n=grid[0].length;
            int count=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='1'){
                        count++;
                        dfs(grid,i,j);
//                        bfs(grid,i,j);
                    }
                }
            }
            return count;
        }

        private void bfs(char[][] grid, int i, int j){
            Queue<int[]> list = new LinkedList<>();
            list.add(new int[] { i, j });
            while(!list.isEmpty()){
                int[] cur = list.remove();
                i = cur[0]; j = cur[1];
                if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                    grid[i][j] = '0';
                    list.add(new int[] { i + 1, j });
                    list.add(new int[] { i - 1, j });
                    list.add(new int[] { i, j + 1 });
                    list.add(new int[] { i, j - 1 });
                }
            }
        }

        private void dfs(char[][] grid, int i, int j){
            if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
            grid[i][j] = '0';
            dfs(grid, i + 1, j);
            dfs(grid, i, j + 1);
            dfs(grid, i - 1, j);
            dfs(grid, i, j - 1);
        }
    }
    class Solution2 {
        class UnionFind {
            int count;
            int[] parent;
            int[] rank;

            public UnionFind(char[][] grid) {
                count = 0;
                int m = grid.length;
                int n = grid[0].length;
                parent = new int[m * n];
                rank = new int[m * n];
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (grid[i][j] == '1') {
                            parent[i * n + j] = i * n + j;
                            ++count;
                        }
                        rank[i * n + j] = 0;
                    }
                }
            }

            public int find(int i) {
                if (parent[i] != i) parent[i] = find(parent[i]);
                return parent[i];
            }

            public void union(int x, int y) {
                int rootx = find(x);
                int rooty = find(y);
                if (rootx != rooty) {
                    if (rank[rootx] > rank[rooty]) {
                        parent[rooty] = rootx;
                    } else if (rank[rootx] < rank[rooty]) {
                        parent[rootx] = rooty;
                    } else {
                        parent[rooty] = rootx;
                        rank[rootx] += 1;
                    }
                    --count;
                }
            }

            public int getCount() {
                return count;
            }
        }

        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int high = grid.length;
            int length = grid[0].length;
            int num_islands = 0;
            UnionFind uf = new UnionFind(grid);
            for (int r = 0; r < high; ++r) {
                for (int c = 0; c < length; ++c) {
                    if (grid[r][c] == '1') {
                        grid[r][c] = '0';
                        if (r - 1 >= 0 && grid[r-1][c] == '1') {
                            uf.union(r * length + c, (r-1) * length + c);
                        }
                        if (r + 1 < high && grid[r+1][c] == '1') {
                            uf.union(r * length + c, (r+1) * length + c);
                        }
                        if (c - 1 >= 0 && grid[r][c-1] == '1') {
                            uf.union(r * length + c, r * length + c - 1);
                        }
                        if (c + 1 < length && grid[r][c+1] == '1') {
                            uf.union(r * length + c, r * length + c + 1);
                        }
                    }
                }
            }

            return uf.getCount();
        }
    }
}
